package book;
/**
 * 2023/5/20 简化，不要引入其他类，用回常规暴力法
 */


import java.util.Arrays;

// 最短路径Dijkstra算法实现代码
public class ShortestPathSolution {

    // 定义顶点的访问状态：
    // RED(红)：已访问且已确定最短路径
    // GREEN(绿): 已访问但未确定当前长度为最短
    // WHITE(白): 未访问
    static final int RED = 2;
    static final int GREEN = 1;
    static final int WHITE = 0;
    
    /**
     * 计算最短路径
     * @param n 表示最多总共有n个顶点
     * @param edges 所有路径信息，以二维数组给出，
     *     数组元素edges[i] = [s, t, w] 表示从 s 到 t 存在权值为 w 的路径
     * @param src 起点编号
     * @return 输出从起点到所有顶点的路径长度，并返回最后一个路径长度
     */
    public int findAllShortestPath(int n, int[][] edges, int src) {
        // dist[x]: 保存起点到 x 的最短路径长度
        // 初始值为无穷大
        int[] dist = new int[n + 1]; 
        Arrays.fill(dist, Integer.MAX_VALUE);
        // visit[x]表示 x 的访问状态：
        //     0(白)-未访问(初始值); 
        //     1(绿)-已访问未确定; 
        //     2(红)-已确定最短长度
        int[] visit = new int[n + 1];

        // 初始时只有起点被访问到，设置路径长度为0
        visit[src] = GREEN;
        dist[src] = 0;

        // 执行dijkstra搜索最短路径
        for (int i = 0; i < n; i++) {
            // 搜索所有的绿点，找到路径最短的一个
            // 标记为红点，并作为当前搜索点
            int s = 0;
            for (int j = 1; j <= n; j++) 
                if (visit[j] == GREEN && dist[j] < dist[s]) 
                    s = j;

            // 如果没有更多可访问的顶点则直接退出
            if (s == 0) break;
            
            // 标记 s 为当前顶点，设置访问状态为红色并开始搜索
            visit[s] = RED;

            // 下面这行代码输出中间过程，可用于调试
            // System.out.println("s=" + s + ", " + dist[s]);

            // 枚举当前顶点 s 的邻接路径，发现新的路径并更新维护排序数组
            for (int[] ed : edges) {
                int u = ed[0], v = ed[1], w = ed[2];

                // 当前边是 s 的邻边，且目标顶点未完成搜索（不是红色）
                if (s == u && visit[v] != RED) {
                    // 计算从起点经过s到达v的路径长度
                    int d = dist[s] + w;

                    // 计算出一条更短的路径长度，更新路径长度及访问状态
                    if (d < dist[v]) {
                        dist[v] = d;
                        visit[v] = GREEN;
                    }
                }
            }
        }

        // 输出结果并返回
        int ans = -1;
        System.out.println("所有的顶点路径信息:");
        for (int i = 1; i <= n; i++) {
            System.out.println("目标顶点 " + i + " -> " + dist[i]);
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        ShortestPathSolution sln = new ShortestPathSolution();
        int[][] edges = {{1,2,2}, {1,5,8},{1,4,3},{2,3,5},{3,5,1},{4,3,2},{4,5,6}};
        int n = 5, src = 1;
        int ans = sln.findAllShortestPath(n, edges, src);
        System.out.println("搜索完毕，最远顶点路径为：" + ans);
    }
}
